stochastischer Algorithmus

stochastischer Algorithmus

 

[griech. stochasis »Vermutung«] (probabilistischer Algorithmus), Algorithmus, der mit Zufallszahlen arbeitet. Sowohl die Reihenfolge der Abarbeitung der einzelnen Anweisungen als auch die Bereitstellung von Zahlenwerten können dem Zufall unterworfen sein. Ein stochastischer Algorithmus kann damit bei gleicher Eingabe unterschiedliche (auch falsche) Ergebnisse liefern, er ist weder determiniert noch deterministisch (Determiniertheit, Determinismus).

 

Bei Problemen, deren Lösungen nur »ja« oder »nein« lauten, unterscheidet man die folgenden Typen von stochastischen Algorithmen:

 

Randomisierte Algorithmen: Wenn ein solcher Algorithmus die Antwort »nein« gibt, so ist dies die korrekte Lösung zu dem Problem. Liefert der Algorithmus die Antwort »ja«, so ist diese Antwort nur mit einer Wahrscheinlichkeit von über 50% korrekt.

 

Las-Vegas-Algorithmen: Sie verfügen zusätzlich zu den Antworten »ja« und »nein« noch über die Antwort »weiß nicht«. »Ja« und »nein« werden nur angegeben, wenn dies mit Sicherheit die korrekte Antwort ist, bei »weiß nicht« konnte keine sichere Entscheidung getroffen werden.

 

Stochastische Algorithmen werden auf Probleme angewandt, zu deren Lösung ein gewöhnlicher Algorithmus zu viel Zeit benötigt. Das bekannteste Beispiel stellt ein 1977 von R. Solvay und V. Strassen vorgestellter Primzahltest vor, der bei der Datenverschlüsselung eine Rolle spielt. Entscheidet dieser randomisierte Algorithmus auf »nein«, ist eine vorgegebene Zahl mit Sicherheit keine Primzahl, bei der Antwort »ja« liegt mit großer Wahrscheinlichkeit eine Primzahl vor.

 

Zur Bearbeitung von schwierigen NP-Problemen (Komplexität) sind stochastische Algorithmen eher ungeeignet.